这道题边的数量最高是10000多,而点只有500,这提醒我们,我们不能直接对边求期望,而是点。
设表示点的期望走过次数,表示点的度数。
那么,
An Ac a day, keeps the doctor away!
这道题边的数量最高是10000多,而点只有500,这提醒我们,我们不能直接对边求期望,而是点。
设Expection[u]表示点u的期望走过次数,Degree[u]表示点u的度数。
那么,
如果没有不能走到的点,这道题就非常简单了。我们只需向下走h−1步,向右走w−1步,就可到达右下角。在这h+w−2步中,我们选h−1向下走,那么答案为Ch+w−2h−1。
但是,棋盘中有些点是不能走的,我们考虑用容斥原理去除多余方案,即
首先,我们将所有源点与汇点筛出来,然后从每一个源点dfs求出它到各汇点的路径数,题目中保证源点与汇点数量相同,我们记为cnt。
那么,我们可以得到一个cnt∗cnt的矩阵。
先考虑路径不相交的情况(似乎大家思路都是这样),题目求的是一个排列的逆序对数,记为τ(σ)。那么,题目等价于求:
与题目定义有些不同,n表示人数,m表示淘汰赛轮数。题目显然输入的是m,根据它算出n。为了方便2进制计算,编号从0~n−1。最后答案加1即可。同时,比赛胜败概率为了方便先除以100,用double计算。
现在考虑如何计算答案,设a[i][j]为i对j的胜率,f[i][j]为第i轮j胜出的概率。那么有:
貌似 @DDF_Van 大佬的标程过不了 , 有些题解用的二分会多一个logn,那就补一发倍增题解吧。
设dp[s][i][j]表示走了不多于s条边,i→j的最大边权(走不通为极小值)
前置知识:莫比乌斯反演,数论分块
这道题还是Trie树的板题,先将n个信息插入字典树中,对于查询的密码,在字典树中查询即可。
插入很好办,我们现在来讨论查询操作。我们记s1为任意一个信息,s2是待匹配的密码。tot[u]表示有多少个字符串经过点u,fin[u]表示有多少个字符串以点u结尾。
那么会出现三种情况: